package com.yiwenup.searching;

import com.yiwenup.asserts.Asserts;

/**
 * 二分查找
 **/
public class BinarySearch {
    /**
     * 查找数据 {@param target} 在有序数组 {@param array} 中的位置
     * <p>
     * 如果存在多个重复的值，序列添加删除某个值时，则返回的索引总是不确定的
     */
    public static int indexOf(int[] array, int target) {
        if (array == null || array.length < 1) return -1;

        // [begin, end)
        int begin = 0;
        int end = array.length;

        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (target < array[mid]) {
                end = mid;
            } else if (target > array[mid]) {
                begin = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    /**
     * 查找数据 {@param target} 在有序数组 {@param array} 中的待插入位置
     * <p>
     * 返回的位置总是第一个大于 {@param target} 的位置
     */
    public static int search(int[] array, int target) {
        if (array == null || array.length < 1) return -1;

        // [begin, end)
        int begin = 0;
        int end = array.length;

        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (target < array[mid]) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }

        return begin;
    }

    public static void main(String[] args) {
        int[] arr1 = {2, 4, 6, 8, 10};
        Asserts.test(indexOf(arr1, 4) == 1);
        Asserts.test(indexOf(arr1, 2) == 0);
        Asserts.test(indexOf(arr1, 10) == 4);
        Asserts.test(indexOf(arr1, 5) == -1);

        int[] arr2 = {2, 4, 8, 8, 8, 12, 14};
        Asserts.test(search(arr2, 5) == 2);
        Asserts.test(search(arr2, 1) == 0);
        Asserts.test(search(arr2, 15) == 7);
        Asserts.test(search(arr2, 8) == 5);
    }
}
